package cn.lena.leecode.arr;

import org.junit.Test;

/**
 * @author lena
 * @date 2021/8/15
 */
public class Offer45 {

	@Test
	public void test() {
		int[] arr={1,2,1,1,1};
		System.out.println(jump2(arr));
	}

	public int jump2(int[] nums) {
		if(nums.length == 1) {
			return 0;
		}
		if(nums.length == 2) {
			return 1;
		}
		int length=nums.length;
		// 记录跳到某个位置的最小值
		int[] min=new int[length];
		for(int i=0;i<length;i++) {
			int cur=nums[i]+i;
			if(cur>=length-1) {
				// cur最大只能到数组最后一个位置
				cur=length-1;
			}
			// 存储跳跃到当前位置的最小值
			min[cur]=min[cur]==0?min[i]+1:Math.min(min[i]+1,min[cur]);
		}
		return min[length-1];
	}

	public int jump(int[] nums) {
		if(nums.length == 1) {
			return 0;
		}
		if(nums.length == 2) {
			return 1;
		}
		int length=nums.length-1;
		nums[length]=0;
		// 从后往前
		for(int i=length-1;i>=0;i--) {
			// 能一步跳到最后一个节点
			if(nums[i]+i >= length) {
				nums[i]=1;
			}else if(nums[i] == 1) {
				// 只能跳一步
				nums[i]=nums[i+1]+1;
			}else{
				// 当前可以跳nums[i]步 从[i+1,i+nums[i]]中找到跳跃次数最少的
				int min=nums[i+1]+1;
				for(int j=i+1;j<=i+nums[i];j++) {
					min=Math.min(min,nums[j]);
				}
				nums[i]=min+1;
			}
		}
		return nums[0];
	}

}
